package com.wangzh.data.arithmetic.sort;

public class A03_InsertDemo {

    public static void main(String[] args) {
         /*
            插入排序：
                将0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一个当成是无序的。
                遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。
                N的范围：0~最大索引

        */
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
//        int[] arr = {3,38, - 44,  5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        //1.找到无序的起始位置

        int startIndex = -1;
        for (int i = 0; i < arr.length-1; i++) {
            if (arr[i]>arr[i+1]) {
                startIndex=i+1;
                break;
            }
        }

        for (int i = startIndex; i < arr.length; i++) {
            for (int i1 = i-1; i1 >= 0; i1--) {
                if (arr[i1+1]<arr[i1]) {

                    int temp =arr[i1+1];
                    arr[i1+1]=arr[i1];
                    arr[i1]=temp;
                }
            }

        }

        printArr(arr);

    }

    private static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}
